package leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author Liangyaoyun
 */
public class leetCode102 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        public List<List<Integer>> levelOrder(TreeNode root) {
            //创建一个结果数组
            List<List<Integer>> res=new ArrayList<>();
            //创建一个队列实现BFS
            Queue<TreeNode> queue=new LinkedList<>();
            //如果当前根节点不为空，则加入队列
            if (root!=null){
                queue.add(root);
            }
            //当队列不为空，则进行遍历
            while (!queue.isEmpty()){
                //创建一个数组来当做答案的数组，将各组答案放在里面
                List<Integer>list=new ArrayList<>();
                //队列中有多少个节点则进行多少次遍历
                int n=queue.size();
                for (int i = 0; i < n; i++) {
                    //弹出一个节点
                    TreeNode tmpNode= queue.poll();

                    list.add(tmpNode.val);
                    //将根节点的左右元素先后存储到队列之中
                    //这样就实现了BFS
                    if (tmpNode.left!=null){
                       queue.add(tmpNode.left);
                    }
                    if (tmpNode.right!=null){
                        queue.add(tmpNode.right);
                    }
                }
                //将答案存到结果数组
                res.add(list);
            }
            return res;
        }
    }
}
